\documentclass[12pt]{article}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{listings}
\usepackage{hyperref}

\lstset{
language=MATLAB,                % choose the language of the code
basicstyle=\footnotesize,       % the size of the fonts that are used for the code
numbers=left,                   % where to put the line-numbers
numberstyle=\footnotesize,      % the size of the fonts that are used for the line-numbers
numbersep=5pt,                  % how far the line-numbers are from the code
showspaces=false,               % show spaces adding particular underscores
showstringspaces=false,         % underline spaces within strings
showtabs=false,                 % show tabs within strings adding particular underscores
frame=single,                   % adds a frame around the code
tabsize=2,                      % sets default tabsize to 2 spaces
captionpos=b,                   % sets the caption-position to bottom
breaklines=true,                % sets automatic line breaking
breakatwhitespace=false,        % sets if automatic breaks should only happen at whitespace
}

\title{CS 4830 Cryptography: Assignment 3} 
\author{Yifan Tong, yt347} 
\date{October 20, 2010}

\begin{document} 
\maketitle 
\newpage
\section{Problem 1} % (fold)
\label{sec:problem_1}
\subsection{Part 1}
Suppose $\exists$ efficient operation
\[M(t) = (t, t, \ldots, t)\]
Given that
\[\{X_n\}_{n\in N}\approx \{Y_n\}_{n\in N}\]
We can conclude that
\[\{M(X_n)\}_{n\in N}\approx \{M(Y_n)\}_{n\in N}\]
Q.E.D.

\subsection{Part 2}
Suppose $\exists$ efficient operation
\[M(Z_n) = (z_1\leftarrow Z_n, z_2\leftarrow Z_n, \ldots, z_k\leftarrow Z_n)\]
Given that
\[\{X_n\}_{n\in N}\approx \{Y_n\}_{n\in N}\]
We can conclude that
\[\{M(X_n)\}_{n\in N}\approx \{M(Y_n)\}_{n\in N}\]
Q.E.D.
% section problem_1 (end)

\section{Problem 2} % (fold)
\label{sec:problem_2}
Given the efficient operation,
\[M(t):=a\cdot t\mbox{ mod } n\]
Since $X\approx U_n$, we can conclude that $M(X) \approx M(U_n)$. Which leads to,
\[aX_n \approx aU_n\]
Since $U_n$ is the uniform distribution over $Z_n$ and $a$ is co-prime with $n$, by closure of group theory, $aU_n=U_n$ (implying that $aU_n\approx U_n$) as $aU_n$ also spans $Z_n$ cyclically and uniformly.\\
By transitivity of the hybrid lemma, since $aX_n \approx aU_n$, $aU_n = U_n$, and $Y\approx U_n$, we conclude that $aX_n\approx Y$.

% section problem_2 (end)

\section{Problem 3} % (fold)
\label{sec:problem_3}
The statement is \textbf{False}; consider the following:
\[ X = \left\{ \begin{array}{ll}
00\ldots 0 & \mbox{w.p. 10\%};\\
11\ldots 1 & \mbox{w.p. 90\%}.\end{array} \right. \]
\[ Y = \left\{ \begin{array}{ll}
00\ldots 0 & \mbox{w.p. 90\%};\\
11\ldots 1 & \mbox{w.p. 10\%}.\end{array} \right. \]
\[ E(t) = \left\{ \begin{array}{ll}
0 & \mbox{if $t=00\ldots 0$};\\
1 & \mbox{if $t=11\ldots 1$}.\end{array} \right. \]
First condition is satisfied because,
\[\{00\ldots 0\}=\{00\ldots 0\}\]
Similarly, the second condition is satisfied because,
\[\{11\ldots 1\}=\{11\ldots 1\}\]
However, it is trivially obvious that,
\[X\not\approx Y\]
\textbf{Bonus}\\
The observation made is that, for the statement in \textbf{Problem 2} to be true, the predicate must be unbiased, meaning,
\[\left|Pr[E(Z_n)=0]-Pr[E(Z_n)=1]\right|< \epsilon (n)\]
% section problem_3(end)


\section{Problem 4} % (fold)
\label{sec:problem_4}

\subsection{Part a}
$h(x)$ is efficient because it hinges on only $f(x)$ and $g(x)$, which are both efficient.\\
$h(x)$ is expansive because both $f(x)$ and $g(x)$ are expansive.\\\\
By definition of PRG,
\[\{x\leftarrow U_n : f(x)\}_n  \approx \{U_m\}_n\]
Therefore, further, by definition
\[\{y\leftarrow \{f(x)\}_n : g(y)\}_n  \approx \{U_{m'}\}_n\]
Therefore, $h(x)=g(f(x))$ is a PRG.

\subsection{Part b}
$h(x)$ is efficient because it hinges on $f(x)$ and the reversal operator, which are both efficient.\\
$h(x)$ is expansive because $f(x)$ is expansive.\\\\
By definition of PRG,
\[\{x\leftarrow U_n : f(x)\}_n  \approx \{U_m\}_n\]
By properties of uniform distribution,
\[\{x\leftarrow U_n : x^R\}_n\approx \{U_n\}_n\]
Given the efficient operation,
\[M(t)=t^R\]
Through the hybrid lemma, we can conclude that
\[\{x\leftarrow U_n : f(x)^R\}_n  \approx \{U_m\}_n\]
Therefore, $h(x)=f(x)^R$ is a PRG.

\subsection{Part c}
The function $h(x)$ is not guaranteed to be pseudo-random because the $\oplus$ operation is performed on $f(x)$ and $g(x)$ with the same seed, $x$.  For example, it is possible for both $f(x)$ and $g(x)$ to both output the same $r\in \{0, 1\}$ for the $b^{th}$ bit in $\{0, 1\}^m$ and $\{0, 1\}^{m'}$, causing the $b^{th}$ bit of $h(x)$ to always be $0$. Therefore, $h(x)$ is not a PRG.

\subsection{Part d}
$h(x)$ is efficient because it hinges on $f(x)$ and the concatenation operator, which are both efficient.\\
$h(x)$ is expansive because $f(x)$ is expansive, and $||$ adds an additional $n$ bits to the output.\\\\
By definition of PRG,
\[\{s'\leftarrow U_n : f(s')\}_n  \approx \{U_m\}_n\]
Since $s$ is a seed, by definition, $s\leftarrow \{U_n\}_n$.  Also, since $s$ and $s'$ are independently chosen, $s$ and $f(s')$ are uncorrelated.\\
Given the following efficient operation,
\[M(t) = \{s\leftarrow \{U_n\}_n: s||t \}\]
We conclude that,
\[\{s\leftarrow \{U_n\}_n; t\leftarrow \{U_m\}_n : s||t \}\approx \{s\leftarrow \{U_n\}_n; t\leftarrow \{f(s')_m\}_n: s||t \}\]
By properties of the uniform distribution, we know that,
\[\{s\leftarrow \{U_n\}_n; t\leftarrow \{U_m\}_n : s||t \}\approx \{U_{m+n}\}_n\]
And finally, by transitivity of the hybrid lemma,
\[\{s\leftarrow \{U_n\}_n; t\leftarrow \{f(s')_m\}_n: s||t \}\approx\{U_{m+n}\}_n\]
Therefore, $h(s||s')$ is a PRG.

\subsection{Part e}
The function $h(s||s')$ is not guaranteed to be pseudo-random because $s$ and $f(s||s')$ are not uncorrelated.  By definition of PRG, $f(x)$ is efficient; as a result, we can construct a distinguisher, $D$, that can distinguish strings produced by $h(s||s')$ by constructing $f(s)$ and comparing the output against the first half of $f(s||s')$.\\
As a result, $h(s||s')$ is not a PRG.

% section problem_4 (end)

\section{Problem 5} % (fold)
\label{sec:problem_5}
\subsection{Part a}
\textbf{Proof: $g$ is (strong) OWF:}\\
Assume $g$ is not an OWF: $\exists$ n.u.P.P.T. $A$ that inverts $g$ w.p. $\frac{1}{p(n)}$; and assume n.u.P.P.T. $B$ inverts $f$.\\
\[B(1^{n-1}, f(x)) = A(1^n, r||f(x))_{2,3,\ldots,n}\mbox{ where } r\in\{0,1\}\]
As a result, $B$ can successfully invert $f$ w.p. $\frac{1}{2p(n)}$, which is a contradiction to $f$ being an OWF.  Therefore, $g$ must be a strong OWF.\\\\
\textbf{Proof: $g$ has a hard-core bit}\\
Suppose,
\[g(x) = g(\sigma\alpha) := 0||f(\alpha) \mbox{ where $\sigma \in \{0, 1\}$}\]
Then $b(\sigma\alpha) = \sigma$ is a predicate to $g$, where $x_1$ is the hard-core bit.
\subsection{Part b}
The following statement is true if and only if $f$ does not lose information (i.e. $f$ is one-to-one) [Ref: \href{http://www.cs.uiuc.edu/class/fa07/cs498mmp/slides/TFC-F07-Lect05.pdf}{Lecture notes from University of Illinois}]:
\[\forall p : \exists f \mbox{ such that $p$ is a hard-core predicate to OWF, }f\]
Therefore, if $f$ is not one-to-one, then,
\[\neg [\forall p : \exists f \mbox{ such that p is a hard-core predicate to OWF, }f]\]
Therefore, the statement
\[\exists p: \forall f \mbox{ s.t. $p$ is a predicate to $f$ }\]
Does not hold because some OWFs are not lossless; for example, $f$ in \textbf{Part a}.
% section problem_5 (end)

\section{Problem 6} % (fold)
\label{sec:problem_6}
\subsection{Part A}
The left-hand-side of the statement uniformly spans $Z_p^*$ by definition of generator.\\
Since $g$ is a generator to $Z_p^*$, and by closure and cyclic properties of the multiplicative group $Z_p^*$,
\[\{x\leftarrow Z_p^*; y\leftarrow Z_p^*:g^{xy} \mbox{ mod } p\} = \{U_n\} \mbox{ on $Z_p^*$}\]
As a result, each member of each distribution occurs with probability of $\frac{1}{p-1}$; and therefore, this statement is \textbf{True}.
\subsection{Part B}
By definition of group generator, and the closure property, given generators $g$ and $h$,
\[\{x\leftarrow Z_p^*:g^x \mbox{ mod }p\}=\{U_n\}\mbox{ on } Z_p^*\]
\[\{x\leftarrow Z_p^*:h^x \mbox{ mod }p\}=\{U_n\}\mbox{ on } Z_p^*\]
This statement is trivially \textbf{True}, as both distributions are identical; i.e. each member of each distribution occurs with probability of $\frac{1}{p-1}$.
\subsection{Part C}
$g=3$ is a generator for $Z_7^*$
\[\{i\leftarrow \{1, 2, \ldots,6\}:3^i \mbox{ mod } 7\} = \{1, 2, \ldots, 6\}\]
\[\{i\leftarrow \{1, 2, \ldots,6\}: i^3 \mbox{ mod } 7\} = \{1, 1, 6, 1, 6, 6\}\]
This statement is \textbf{False} by counter-example, as the element $1$ occurs with probabilities $\frac{1}{6}$ and $\frac{1}{2}$.
\subsection{Part D}
Consider $g=3, h=2$ for $Z_5^*$
\[\{i\leftarrow Z_5^*:x^3 \mbox{ mod } 5\} = \{1, 3, 2, 4\}=\{U_n\}\mbox{ on }Z_5^*\]
\[\{i\leftarrow Z_5^*:x^6 \mbox{ mod } 5\} = \{1, 4, 4, 1\}\]
This statement is \textbf{False} by counter-example, as the element $1$ occurs with probabilities $\frac{1}{4}$ and $\frac{1}{2}$.
% section problem_6 (end)
\end{document}
